#!/usr/bin/python
# -*- coding: UTF-8 -*- 
from pyforest import *


# 二分法案列
# 在将区间一分为二后，答案只能出现在其中的一个区间，不能同时出现在两个区间内，这样的情形下才适合二分
# list 需要查询的数组
# item 查询的数

def binary_search(lists, item):
    low = 0  # 查询数组最小位置，默认为0
    high = len(lists) - 1  # 查询数组最大位置

    while low <= high:
        mid = int((low + high) / 2)  # 取中间值
        guess = lists[mid]  # 中间值的数
        if guess == item:
            print(str(item) + "在1-100的第" + str(mid) + "位置")
            return mid
        if guess > item:  # 中间数在左边
            high = mid - 1
        else:
            low = mid + 1  # 中间数在右边
    return None  # 不在数组内返回


if __name__ == '__main__':
    arr = list(range(0, 100))
    print(arr)
    while True:
        key = input("请输入0-100内你要查找的数字：")
        if key == "":
            print("输入错误!")
            break
        else:
            binary_search(arr, int(key))
